//============================================================================
// Name        : BB_PCV.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <queue>

#include <mpi.h>

#include "Defines.h"
#include "Graph.h"
#include "Problem.h"
#include "Solution.h"
#include "Solver.h"


using namespace std;
using namespace MPI;


void generate(int argc, char *argv[]);
void solveSequential(int argc, char *argv[]);
void solveParallel(int argc, char *argv[]);


int main(int argc, char *argv[]) {
	if (argc == 4)
	{
		if (!strcmp(argv[1], "generate"))
		{
			generate(argc, argv);
		}
	} else if (argc == 3)
	{
		if (!strcmp(argv[1], "solve_sequential"))
		{
			solveSequential(argc, argv);
		} else if (!strcmp(argv[1], "solve_parallel"))
		{
			solveParallel(argc, argv);
		} else
		{
			cout << "modo de execucao escolhido \"" << argv[1] << "\" incorreto. Utilize o formato" << endl;
			cout << argv[0] << " generate [size] [outputfile]" << endl;
			cout << argv[0] << " solve_sequential/sove_parallel [inputfile]" << endl;
		}
	} else
	{
		cout << "Entrada incorreta. Utilize o formato" << endl;
		cout << argv[0] << " generate [size] [outputfile]" << endl;
		cout << argv[0] << " solve_sequential/sove_parallel [inputfile]" << endl;

	}

	return 0;
}

void generate(int argc, char *argv[]) {
	int size = atoi(argv[2]);
	string output(argv[3]);

	Graph g(size);

	g.generate();

	if (!g.save(output))
		cout << "Problemas ao salvar o arquivo." << endl;

}

void solveSequential(int argc, char *argv[]) {
	unsigned long iterations = 1;
	unsigned long maxQueueSize = -1;

	Solution bestUpperBound;
	Graph graph(argv[2]);

	Problem problem(graph.getSize());

	queue<Problem> queue;

	queue.push(problem);

	while (queue.empty() == false)
	{
		if (maxQueueSize == -1 || maxQueueSize < queue.size())
			maxQueueSize = queue.size();

		Problem *problem = new Problem(queue.front());

		queue.pop();

		int *modifyed = new int(0);

		vector<Problem> newProblems = Solver::solveProblem(graph, *problem, bestUpperBound, modifyed);

		if (*modifyed)
			cout << bestUpperBound.getCost() << endl;

		delete modifyed;

		for (int i = 0; i < newProblems.size(); ++i)
			queue.push(newProblems[i]);

		delete problem;

		iterations++;

	}

	cout << "tamanho maximo da fila: " << maxQueueSize << endl;
	cout << "total de iteracoes: " << iterations << endl;
	cout << endl;
	cout << "custo: " << bestUpperBound.getCost() << endl;
	cout << "caminho: ";
	bestUpperBound.printSolution();
	cout << endl;
}


void solveParallel(int argc, char *argv[]) {

	int rank, size, finished;

	//Inicializacao da MPI
	Init(argc, argv);

	rank = COMM_WORLD.Get_rank();
	size = COMM_WORLD.Get_size();

	Solution newBestSolution;

	Graph graph(argv[2]);

	Solution bestUpperBound;

	queue<Problem> queue;

	Problem problem(graph.getSize());

	if (rank == MASTER)
	{
		queue.push(problem);

		//resolve ate que a fila atinja o tamanho adequado
		while (queue.size() < size && !queue.empty())
		{

			Problem *problem = new Problem(queue.front());

			queue.pop();

			int *modifyed = new int(0);

			vector<Problem> newProblems = Solver::solveProblem(graph, *problem, bestUpperBound, modifyed);

			if (*modifyed)
				cout << bestUpperBound.getCost() << endl;

			delete modifyed;

			for (int i = 0; i < newProblems.size(); ++i)
				queue.push(newProblems[i]);

			delete problem;

		}

		//cout << "terminei parte inicial de processamento no mestre" << endl;

		if (queue.empty())
		{
			//cout << "processo terminou no mestre" << endl;

			cout << "custo: " << bestUpperBound.getCost() << endl;
			cout << "caminho: ";
			bestUpperBound.printSolution();
			cout << endl;

			finished = 1;

		} else
		{
			finished = 0;
		}
	}

	COMM_WORLD.Bcast(&finished, 1, INT, 0);

	if (!finished)
	{

		int receivedVectorSolution[size][graph.getSize()];
		Request received[size];

		bool nodeDone;
		int doneVector[size];
		Request doneReceived[size];


		for (int i = 0; i < size; ++i)
		{
			if (i != rank)
			{
				doneVector[i] = false;
				doneReceived[i] = COMM_WORLD.Irecv(&nodeDone, 1, CHAR, i, DONE_TAG);
			}
		}

		for (int i = 0; i < size; ++i)
		{
			if (i != rank)
			{
				received[i] = COMM_WORLD.Irecv(receivedVectorSolution[i], graph.getSize(), INT, i, SOLUTION_TAG);
			}
		}

		bool hascost = bestUpperBound.hasCost();

		COMM_WORLD.Bcast(&hascost, 1, CHAR, MASTER);

		if(hascost)
		{
			int solution[graph.getSize()];
			vector<int> answer;

			if(rank == MASTER)
			{
				answer = bestUpperBound.getAnswer();

				for(int i = 0; i < answer.size(); ++i)
				{
					solution[i] = answer[i];
				}
			}

			COMM_WORLD.Bcast(solution, graph.getSize(), INT, MASTER);

			if (rank != MASTER)
			{
				for (int i = 0; i < size; ++i)
				{
					answer.push_back(solution[i]);
				}

				bestUpperBound.build(answer);
			}

		}


		if (rank == MASTER)
		{
			//divisao do problema entre os nós escravos
			for (int i = 1; i < size; ++i)
			{

				//cout << "vou enviar para " << i << endl;

				Problem *problem = new Problem(queue.front());
				queue.pop();

				problem->send(i);

				//cout << "enviei para " << i << endl;

				delete problem;
			}
		} else
		{
			//cout << rank << " vou receber" << endl;
			problem.receive(MASTER);
			//cout << rank << "recebi" << endl;

			queue.push(problem);
		}
//		cout << "vou comecar o loop" << endl;

		//resolve a parte do problema referente ao mestre
		while (!queue.empty())
		{

			Problem *problem = new Problem(queue.front());

			queue.pop();


			int *modifyed = new int(0);

			int externModifyed = 0;


			vector<Problem> newProblems = Solver::solveProblem(graph, *problem, bestUpperBound, modifyed);


			for (int i = 0; i < newProblems.size(); ++i)
			{
				queue.push(newProblems[i]);

			}

			delete problem;

			for (int i = 0; i < size; ++i)
			{
				if (i != rank && doneReceived[i].Test())
				{
					if(nodeDone)
					{
						doneVector[i] = true;
					}
				}
			}

			for (int i = 0; i < size; ++i)
			{
				if (i != rank && received[i].Test() )
				{
					vector<int> v;

					for(int j = 0; j < graph.getSize(); ++j)
					{
						v.push_back(receivedVectorSolution[i][j]);
					}

					Solution newBestSolution (v);

					newBestSolution.calculateCost(graph);

					if (!bestUpperBound.hasCost() || (bestUpperBound.hasCost() && bestUpperBound.getCost() > newBestSolution.getCost()))
					{
						bestUpperBound = newBestSolution;
						externModifyed = 1;
					}

					received[i] = COMM_WORLD.Irecv(receivedVectorSolution[i], graph.getSize(), INT, i, SOLUTION_TAG);

				}
			}


			if (*modifyed && !externModifyed)
			{
				int vectorSolution[graph.getSize()];

				vector<int> v = bestUpperBound.getAnswer();

				for(int i = 0; i < v.size(); ++i)
				{
					vectorSolution[i] = v[i];
				}


				for (int i = 0; i < size; ++i)
				{
					if (i != rank && !doneVector[i])
					{
						COMM_WORLD.Send(vectorSolution, v.size(), INT, i, SOLUTION_TAG);
					}
				}
			}

			externModifyed = 0;
			delete modifyed;

		}


		for (int i = 1; i < size; ++i)
		{
			if (i != rank)
			{
				nodeDone = true;
				COMM_WORLD.Send(&nodeDone, 1, CHAR, i, DONE_TAG);
			}
		}

		if (rank == MASTER)
		{
			for(int i = 1; i < size; ++i)
			{
				COMM_WORLD.Recv(receivedVectorSolution[i], graph.getSize(), INT, i, FINISH_TAG);

				vector<int> v;

				for(int j = 0; j < graph.getSize(); ++j)
				{
					v.push_back(receivedVectorSolution[i][j]);
				}

				Solution newBestSolution (v);

				newBestSolution.calculateCost(graph);

				if (!bestUpperBound.hasCost() || (bestUpperBound.hasCost() && bestUpperBound.getCost() > newBestSolution.getCost()))
				{
					bestUpperBound = newBestSolution;
				}
			}

			cout << "custo: " << bestUpperBound.getCost() << endl;
			cout << "caminho: ";
			bestUpperBound.printSolution();
			cout << endl;
		}
		else
		{
			int vectorSolution[graph.getSize()];

			vector<int> v = bestUpperBound.getAnswer();

			for(int i = 0; i < v.size(); ++i)
			{
				vectorSolution[i] = v[i];
			}

			COMM_WORLD.Send(vectorSolution, v.size(), INT, MASTER, FINISH_TAG);

		}

	}

	Finalize();
}

